package com.wenhai.liuyubobobo.imooc.search;

/**
 * 递归/非递归 实现二分查找
 *
 * @author wenhai
 * @date   2021/3/2
 */
public class BinarySearch {
    private BinarySearch() {

    }

    public static <E extends Comparable<E>> int searchR(E[] e, E target) {
        return searchR(e, 0, e.length - 1, target);
    }

    public static <E extends Comparable<E>> int search(E[] e, E target) {
        int l = 0;
        int r = e.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >>> 1);
            if (e[mid].compareTo(target) == 0) {
                return mid;
            }
            if (e[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return -1;
    }

    private static <E extends Comparable<E>> int searchR(E[] e, int l, int r, E target) {
        if (l > r) {
            return -1;
        }

        int mid = l + ((r - l) >>> 1);
        if (e[mid].compareTo(target) == 0) {
            return mid;
        }

        if (e[mid].compareTo(target) > 0) {
            return searchR(e, l, mid - 1, target);
        }

        return searchR(e, mid + 1, r, target);
    }

    public static void main(String[] args) {
        Integer[] e = {-1, 0, 3, 5, 9, 12};
        System.out.println(search(e, 9));
    }

}
